package org.example.algorithm.dp;

public class CanPartitionSolution {

    public static void main(String[] args) {
        int[] nums = {2, 2, 3, 5};
        CanPartitionSolution solution = new CanPartitionSolution();
        boolean res = solution.canPartition(nums);
        System.out.println(res);
    }

    //优化内存空间占用
    public boolean canPartition(int[] nums) {
        if (nums.length <= 1) {
            return false;
        }
        int sum = 0;
        int max = Integer.MIN_VALUE;
        for(int num: nums) {
            sum += num;
            max = Math.max(max, num);
        }
        if (sum % 2 == 1 || max > sum/2) {
            return false;
        }
        int target = sum/2;
        boolean[] dp = new boolean[target+1];
        dp[0] = true;
        for (int i=0;i<nums.length;i++) {
            //内层循环正向遍历会覆盖上一次dp[i]的值，所以采用逆向遍历
            for (int j=target;j>0;j--) {
                if (nums[i] <= j) {
                    dp[j] = dp[j] || dp[j - nums[i]];
                }
            }
        }
        return dp[target];
    }

    public boolean canPartition2(int[] nums) {
        if (nums.length <= 1) {
            return false;
        }
        int sum = 0;
        int max = Integer.MIN_VALUE;
        for(int num: nums) {
            sum += num;
            max = Math.max(max, num);
        }
        if (sum % 2 == 1 || max > sum/2) {
            return false;
        }
        int target = sum/2;
        //定义dp[i][j]，【0，i-1】是否可以选择一组数组成和为j
        boolean[][] dp = new boolean[nums.length][target+1];
        //i=0
        dp[0][nums[0]] = true;
        for (int i=1;i<nums.length;i++) {
            for (int j=0;j<=target;j++) {
                if (j == 0) {
                    dp[i][j] = true;
                    continue;
                }
                if (nums[i] <= j) {
                    dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]];
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[nums.length-1][target];
    }
}
